package cn.edu.njust.alg;

/**
 * 创建时间：2015年5月25日 下午4:59:52 项目名称：AlgorithmExercise
 * 
 * @author Zhou Xiumin
 * @version 1.0
 * @since JDK 1.7.0_21 文件名称：KMPImpl.java 类说明：
 */
public class KMPImpl {

	public static int kmp_index(char[] s, char[] m) {
		int i = 0, j = 0;
		int[] next = getNext(m);
		ArrayUtils.printArray(next);
		while (i < s.length && j < m.length) {
			if (j == -1 || s[i] == m[j]) {
				i++;
				j++;
			} else {
				j = next[j];
			}
		}
		if (j < m.length) {
			return -1;
		}

		return i - j;
	}

	public static int[] getNext(char[] m) {
		int[] next = new int[m.length];
		next[0] = -1;
		int i = 0, j = -1;
		while (i < m.length - 1) {
			if (j == -1 || m[i] == m[j]) {
				i++;
				j++;
				if (m[i] != m[j]) {
					next[i] = j;
				} else {
					next[i] = next[j];
				}
			} else {
				j = next[j];
			}
		}

		return next;
	}

	public static int[] getNextOld(char[] m) {
		int[] next = new int[m.length+1];
		next[0] = -1;
		int i = 0, j = -1;
		while (i < m.length) {
			if (j == -1 || m[i] == m[j]) {
				i++;
				j++;
				next[i] = j;

			} else {
				j = next[j];
			}
		}

		return next;
	}

	/**
	 * <p>
	 * Title: index
	 * </p>
	 * <p>
	 * Description: 普通的匹配
	 * </p>
	 * 
	 * @param s
	 * @param m
	 * @return
	 */
	public static int index(char[] s, char[] m) {
		int i = 0, j = 0;
		while (i < s.length && j < m.length) {
			if (s[i] == m[j]) {
				i++;
				j++;
			} else {
				i = i - j + 1;
				j = 0;
			}
		}
		if (j < m.length) {
			return -1;
		}

		return i - j;
	}

	public static void main(String[] args) {

		String mstr = "abababf";
		int[] seq = new int[mstr.length()];
		for (int i = 0; i < seq.length; i++) {
			seq[i] = i;
		}
		ArrayUtils.printArray(seq);
		ArrayUtils.printArray(getNextOld(mstr.toCharArray()));

		// System.out.println(kmp_index(t.toCharArray(), m.toCharArray()));

	}

}
